#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//给一个递增序列的数组，将其前面的数组搬到数组的末尾，（旋转数组），例如array[]={3,4,5,1,2};
//在旋转数组中找到最小的数字
//这里的数组是比较特殊的，数组前面一部分为有序的，后面一部分为有序的，利用这个特点很容易就想到二分查找
int  OrderSearch(int numbers[],int start,int end)
{
    int i=start;
    int min=numbers[start];
    for(i=start+1;i<=end;++i)
    {
        if(numbers[i]<min)
        {
            min=numbers[i];
        }
    }
    return min;
}
int GetMin_1(int numbers[],int length)
{
    assert(numbers);
    assert(length>0);
    if(numbers[0]<numbers[length-1])
    {//这种情况是没有进行旋转
        return numbers[0];
    }
    int start=0;
    int end=length-1;
    while(start<end-1)
    {
        int mid=start+(end-start)/2;
        if(numbers[start]==numbers[mid]&&numbers[mid]==numbers[end])
        {//这种情况就是说不能确定numbers[mid]是属于前一个有序序列还是后一个，这里就需要顺序查找
         //**********这种情况是比较特殊的*************
         //int numbers[]={1,1,1,0,1};
            return OrderSearch(numbers,start,end);
        }
        if(numbers[mid]>=numbers[start])
        {//如果中间的元素大于或者等于开始查找的范围，
        //则从mid开始向后找，即mid下一查找范围中的第一个元素，属于下一组中比较大的那个有序数组
            start=mid;
        }
        else
        {//否则就从mid开始的之前找，mid属于下一组中比较小的那个有序数组
            end=mid;
        }
    }
    //这样保证每次end都属于查找范围中比较小的那一组元素
    //当剩下两个数字时，那么end一定就是最小的那个元素
    //出循环，说明start和end相邻，则end为第二组的最小的，start为第一组的最大的
    return numbers[end];
}
int main()
{

    int numbers[]={3,4,5,1,2};
    //int numbers[]={1,1,1,0,1};
    //int numbers[]={1,2,3,4,5};
    //int numbers[]={0};
    int length=sizeof(numbers)/sizeof(numbers[0]);
    int ret=GetMin_1(numbers,length);
    printf("Min: %d\n",ret);
    return 0;
}
